package LinkedListPlus;

import java.util.List;
/**
 * User:浪尘
 * Date:2022-09-21
 * Time:19:14
 */
public class MyLinkedList {

    static class ListNode {
        public int val;
        public ListNode prev;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode head;
    public ListNode tail;


    public void display(){//打印双向链表
        ListNode cur = this.head;
        while (cur!=null){
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
    }


    public int size(){//获取链表长度
        ListNode cur = this.head;
        int count = 0;
        while (cur!=null){
            count++;
            cur = cur.next;
        }
        return count;
    }


    public boolean contains(int key){//判断关键字key是否在该链表中
        ListNode cur = this.head;
        while (cur!=null){
        if(cur.val == key){
            return true;
            }
        }
        return false;
    }


    public void addFirst(int data){//头插法
        ListNode node = new ListNode(data);
        if(this.head == null){
            this.head = node;
            this.tail = node;
        }else{
            node.next = this.head;
            this.head.prev = node;
            head = node;
        }
    }


    public void addLast(int data){//尾插法
        ListNode node = new ListNode(data);
        if(this.head == null){
            this.head = node;
            this.tail = node;
        }else{
            tail.next = node;
            node.prev = tail;
            tail = node;
        }
    }


    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index,int data){
        //1、判断Index位置的合法性
        //2、判断特殊位置，头插 和 尾插
        //3、找到index位置节点的地址
        if(index<0 || index >size()){
            return;
        }
        if(index == 0){
            addFirst(data);
        }
        if(index == size()){
            addLast(data);
        }
        ListNode cur = findIndexListNode( index);
        ListNode node  = new ListNode(data);
        node.next = cur;
        cur.prev.next = node;
        node.prev = cur.prev;
        cur.prev = node;
    }

    private ListNode findIndexListNode(int index) {
        ListNode cur = head;
        while ((index != 0)) {
            cur = cur.next;
            index--;
        }
        return cur;
    }


    public void remove(int key){//删除第一次出现关键字为key的节点
        ListNode cur = head;
        while (cur!=null){
            if(cur.val == key){
                if(cur==head) {
                    head = head.next;
                    if(head!=null){//表示只有一个节点的情况下
                        head.prev = null;
                    }else{
                        tail = null;
                    }
                }else{
                    cur.prev.next = cur.next;
                    if(cur.next!=null){
                        cur.next.prev = cur.prev;
                    }else{
                        this.tail = cur.prev;
                    }
                }
               return;
            }
            cur = cur.next;
        }
    }

    public void removeAllkey(int key){//删除所有值为key的节点
        ListNode cur = head;
        while (cur!=null){
            if(cur.val == key){
                if(cur==head) {
                    head = head.next;
                    if(head!=null){//表示只有一个节点的情况下
                        head.prev = null;
                    }else{
                        tail = null;
                    }
                }else{
                    cur.prev.next = cur.next;
                    if(cur.next!=null){
                        cur.next.prev = cur.prev;
                    }else{
                        this.tail = cur.prev;
                    }
                }
            }
            cur = cur.next;
    }
    }


    public void clear(){//一个一个置空
        ListNode cur = head;
        ListNode curNext = cur.next;
        while(cur!=null){
            head.next = null;
            head.prev = null;
            cur = curNext;
        }
    }
    public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addLast(10);
        myLinkedList.addLast(10);
        myLinkedList.addLast(10);
        myLinkedList.addLast(10);
        myLinkedList.addLast(20);
//        myLinkedList.addIndex(2,888);
//       myLinkedList.remove(12);
//        myLinkedList.removeAllkey(10);
        myLinkedList.clear();
        myLinkedList.display();
//        boolean b1 = myLinkedList.contains(12);
//        System.out.println(b1);
//        myLinkedList.display();
//        int ret = myLinkedList.size();
//        System.out.println("链表的长度为："+ret);
//        myLinkedList.addIndex(2,888);
//        myLinkedList.remove(12);
//        myLinkedList.removeAllkey(12);
//        myLinkedList.clear();
//        myLinkedList.display();
    }
}
